# coding=utf-8

"""
    此方式的算法可以描述为以下形式的函数：
    F(n) = 空集：n=0;
    F(n) = least([c U F(n-c) | c 属于 options且 c<=n]):n>0
"""


def merge(c, li: list):
    return [c] + li


def least(li: list):
    # print(li)
    res = li[0]
    for l in li:
        if len(l) < len(res):
            res = l
    return res


# 朴素自顶向下递归方式找最优解
def change(x: int, options: list):
    """
    在自顶向下递归求解中，有大量的重复计算,性能会很差
    """
    if x == 0:
        return []
    else:
        result_list = []
        for c in options:
            if c <= x:
                res = merge(c, change(x - c, options))
                result_list.append(res)
        return least(result_list)


tab = [[] for _ in range(1 << 10)]


def changeDPv0(x: int, options: list):
    """
    采用动态规划优化；
    使用一个tab存储F(n)的计算结果，当需要重复计算时直接取结果，避开重复计算。
    """
    if tab[x] is not None:
        return tab[x].copy()
    if x == 0:
        return []
    else:
        result_list = []
        for c in options:
            if c <= x:
                res = merge(c, changeDPv0(x - c, options))
                result_list.append(res)
        result_list = least(result_list)
        tab[x] = result_list.copy()
        return result_list


tabv1 = [[] for _ in range(1 << 10)]


def changeDPv1(x: int, options: list) -> list:
    if x == 0:
        return []
    if len(tabv1[x]) == 0:
        for c in options:
            if c <= x:
                res = merge(c, changeDPv1(x - c, options))
                if tabv1[x] == [] or len(res) < len(tabv1[x]):
                    tabv1[x] = res
    return tabv1[x]


tabv2 = [[] for _ in range(1 << 10)]


def changeDPv2(x: int, options: list) -> list:
    """
    changeDPv1优化v2
    """
    if x > 0 and len(tabv2[x]) == 0:
        for c in options:
            if c <= x:
                res = merge(c, changeDPv2(x - c, options))
                if tabv2[x] == [] or len(res) < len(tabv2[x]):
                    tabv2[x] = res
    return tabv2[x]


tabv3 = [[] for _ in range(1 << 20)]


def changeDPv3(x, cs) -> list:
    """
    算法新解的实现
    """
    if x > 0 and tabv3[x] == []:
        for s in [[c] + changeDPv3(x - c, cs) for c in cs if c <= x]:
            if tabv3[x] == [] or len(s) < len(tabv3[x]):
                tabv3[x] = s
    return tabv3[x]


# 自底向上的动态规划
def change_bottom2up(x, options):
    """
    从0开始的最优解查找，不断调整，存入缓存表中，避开重复计算
    """
    T = [[] for _ in range(x + 1)]
    for ti in range(1, x + 1):
        for c in options:
            if c <= ti and (T[ti] == [] or 1 + len(T[ti - c]) < len(T[ti])):
                T[ti] = [c] + T[ti - c]
    return T[x]


if __name__ == '__main__':
    opt = [1, 3, 4]
    # print(change(1, opt))  # [1]
    # print(change(2, opt))  # [1,1]
    # print(change(3, opt))  # [3]
    # print(change(4, opt))  # [4]
    # print(change(6, opt))  # [3,3]

    print(changeDPv1(6, opt))  # [3.3]
    print(changeDPv3(6, opt))
    print(change_bottom2up(6, opt))
